#include <vector>

using namespace std;

int main( int argc, char **argv )
{
  int64_t totalNodes, depthSum;
  state_t state, child;
  vector<state_t> queue, next_queue;
  int d, rule_used;
  func_ptr iter;
  state_map_t *map = new_state_map();
  FILE *file;

  if( argc < 2 ) {

    fprintf( stderr, "usage: bfs output_file\n" );
    exit( -1 );
  }

  /* add goal states to depth 0 queue */
  totalNodes = 0;
  depthSum = 0;
  first_goal_state( &state, &d ); do {

    state_map_add( map, &state, 0 );
    queue.push_back( state );
    ++totalNodes;
  } while( next_goal_state( &state, &d ) );

  /* generate all states, one depth level at a time */
  d = 1;
  do {

    /* look at children of all states in queue for current distance */
    while( queue.size() ) {

      /* get state */
      state = queue.back();
      queue.pop_back();

      /* look at all children */
      init_bwd_iter( iter );
      while( ( rule_used = next_bwd_iter( iter, &state ) ) >= 0 ) {
	apply_bwd_rule( rule_used, &state, &child );

	if( state_map_get( map, &child ) == NULL ) {
	  /* child has not yet been visited
	     note distance and add to next queue */

	  state_map_add( map, &child, d );
	  next_queue.push_back( child );
	}
      }
    }

    /* switch to next queue and increase current distance */
    queue = next_queue;
    next_queue.clear();
    printf( "%zu states at distance %d\n", queue.size(), d );
    totalNodes += queue.size();
    depthSum += d * queue.size();
    ++d;
  } while( queue.size() );

  double avg = (double)depthSum / (double)totalNodes;
  printf( "%"PRIu64" states, average distance of %lf\n", totalNodes, avg );

  /* save the map */
  file = fopen( argv[ 1 ], "w" );
  if( file == NULL ) {

    fprintf( stderr, "could not open %s for writing\n", argv[ 1 ] );
    exit( -1 );
  }
  write_state_map( file, map );
  fclose( file );

  return 0;
}
